// ****************************************************************
// the climbing stairs problem
// ****************************************************************

#![allow(dead_code)]

use core::num;

fn fibonacci(n: i32) -> i32 {
    if n == 1 {
        return 1;
    }
    if n == 2 {
        return 2;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

pub fn climb_stairs() {
    // solve fn(n) = fn(n-1) + fn(n-2) question
    let res = fibonacci(5);
    println!("{}", res);
}

// ****************************************************************
// the find the primes problem
// ****************************************************************

pub fn find_primes(n: i32) -> i32 {
    if n <= 2 {
        return 0;
    }
    // n is
    let nu = n as usize;
    let mut is_prime = vec![true; nu + 1];
    is_prime[0] = false; // 0
    is_prime[1] = false; // 1

    for i in 2..=(nu as f64).sqrt() as usize {
        // find index i is prime or not start from 2
        if is_prime[i] {
            for j in (i * i..=nu).step_by(i) {
                is_prime[j] = false;
            }
        }
    }

    // counting numbers in is_prime true
    let a = is_prime.iter().filter(|&&x| x).count();
    return a as i32;
}

// ************************************************
// deleting the duplicated items in a list
// ************************************************
pub fn delete_duplicated_items() {
    let mut nums = vec![0, 0, 0, 1, 1, 2, 2];

    let mut slow = 2;
    for fast in 2..nums.len() {
        if nums[fast] != nums[slow - 2] {
            nums[slow] = nums[fast];
            slow += 1;
        }
    }
    nums.truncate(slow);
}

// ************************************************
// split the words
// ************************************************
pub fn inverse_words(s: String) -> String {
    let mut parts: Vec<&str> = s.split(" ").filter(|&itm| !itm.is_empty()).collect();
    parts.reverse();
    let ans = parts.join(" ");
    ans
}

// ************************************************
// align max words
// make words vec aligned perfectly by max_width
// 经典排版问题
// ************************************************
pub fn full_justify() {
    let words = vec![
        "This",
        "is",
        "an",
        "example",
        "of",
        "text",
        "justification.",
    ];
    let max_width = 16;

    let mut item = String::new();
    let mut ans = Vec::new();

    for i in 0..words.len() {
        if item.chars().count() + words[i].chars().count() <= max_width {
            item.push_str(words[i]);
            item.push_str(" ");

            dbg!(item.len(), &item);
        } else {
            item.push_str(&" ".repeat(max_width - item.chars().count()));
            ans.push(item.clone());
            println!("{:?}", ans);

            item.clear();
            item.push_str(words[i]);
            item.push_str(" ");
        }
    }

    ans.push(item.clone());

    println!("{:?}", ans);
}
